module Nullable where

import Cpo
import Fixpoint

import Data.Set as S

type Nonterminal = String
type Terminal = String

type Grammar = Set (Nonterminal, [Symbol])

data Symbol = N Nonterminal | T Terminal
              deriving (Eq, Ord, Show)

isN (N _) = True
isN _     = False


nullable :: Grammar -> Set Symbol
nullable g = condFixpoint (indirectEps g) (eps g)

indirectEps :: Grammar -> Set Symbol -> Set Symbol
indirectEps g n =
  S.fold (\ (lhs,rhs) n1 ->
           if isNullable n1 rhs then S.insert (N lhs) n1
           else n1) n g
  where
    isNullable n1 rhs = S.fromList rhs `S.isSubsetOf` n1

eps :: Grammar -> Set Symbol
eps g =
  S.map (N . fst) $ S.filter (\ (lhs, rhs) -> Prelude.null rhs) g



g = fromList [
     ("Z", [T "d"]),
     ("Z", [N "X", N "Y", N "Z"]),
     ("Y", []),
     ("Y", [T "c"]),
     ("X", [N "Y"]),
     ("X", [T "a"])
    ]
